\chapter{Coordination}

% Label
\label{pgfId-10505}

% Label
\label{72463}

\begin{itemize}

\item{Generic Mailbox Invocations}

\item{Memo: A Remote Interface to SharedTableOfQueues}

\item{Vector Inner Product}

\item{Trapezoidal Integration}

\item{Warshall’s Algorithm}

\item{Chapter Wrap-up}

\end{itemize}

% Label
\label{pgfId-10507}
The networking classes found in the java.net package give you just about everything you need to build Internet services and other client-server applications, but is not quite what you need for doing parallel and distributed computing. This chapter addresses the basics of how to extend the ideas presented in the previous chapters to the realm of networking with an emphasis on coordination.
\par

% Label
\label{pgfId-12708}
The topic of coordination has long been of interest to academic researchers and industry practicioners in the “field” of high-performance computing. The first notable ideas for coordination are found in the
\emph{Communicating Sequential Processes}
, by Tony Hoare, one of two people behind the monitor concept presented in Chapter 4, and the Linda project done at Yale University. This chapter shows how to build a basic coordination model that is very similar to the seminal works but radically simplified
\par

% Label
\label{pgfId-12706}
Before proceeding, we have not included here a discussion of other Java technologies that (in all fairness) allow us to venture beyond the client-server paradigm. These include RMI, CORBA, Java Spaces, and Jini. Of these four, Java Spaces is most similar to what we define as a coordination system. Java Spaces is a key component of the Jini architecture, and we believe that there are a number of excellent books in print that provide an excellent overview of these technologies. We have chosen not to cover these technologies in this book and focus on lighter and leaner frameworks that specifically address the need for (easily) writing parallel and distributed codes. For those who are interested in learning more about the relevant Java distributed computing technologies, we provide a comprehensive list of references at the end of the chapter.
\par

% Label
\label{pgfId-12715}
The chapter begins with an overview of the generic mailbox invocation system (GMI). GMI is a simple remote procedure calling framework that makes use of Java object serialization. The GMI system is used to build Memo, which is a simple coordination model derived from the Linda project. The Memo system can be considered a remote interface to the shared table of queues abstractions presented in Chapter 9. This chapter presents a few examples of how to translate some codes presented earlier into versions that make use of the coordination facilities found in the Memo system. The examples presented include vector inner product (
\texttt{VMpy}
), trapezoidal integration (
\texttt{IntegTrap}
), and Warshall’s algorithm (
\texttt{Warshall}
).
\par

\section{Generic Mailbox Invocations}

% Label
\label{pgfId-12714}

% Label
\label{10883}

% Label
\label{pgfId-10754}
GMI is a framework for peer-to-peer communication that we developed to facilitate the development and deployment of clustering software. It was developed somewhat as a response to remote method invocation (RMI). RMI is Java’s built-in framework for doing remote procedure calling, which is accompanied by another framework called object serialization.
\par

% Label
\label{pgfId-10758}
We will not discuss the details of RMI here, again leaving this discussion to books that have been written entirely on the subject. On the other hand, we will address the reasons why RMI does not work terribly well for clustered applications:
\par

\begin{itemize}

\item{Serialization overhead : The use of RMI virtually goes hand-in-hand with object serialization. Serialization is a very elegant framework that is designed to support the migration of tree-structured objects. Most clustered computing algorithms make little or no use of such complex data structures. In fact, the most commonly used data structures are scalars (boolean, character, integer, and floating point) and basic aggregations (one-, two-, and three-dimensional arrays of scalar). Java serialization does a particularly poor job of handling these basic cases, and a number of papers have been written that describe the problems in detail. Effectively, the Serialization facility supports call-by-copy semantics, which breaks the call-by-reference semantics that are Java’s normal parameter passing scheme.}

% Label
\label{pgfId-10759}

\item{Registry : The registry is a useful program for maintaining a semipersistent repository of objects that can be used remotely; however, it also adds a layer of indirection when it comes to communication. Latency is a major factor in the performance of any distributed communication system. TCP/IP sockets programming itself presents much unwanted latency in a clustered environment, since the assumption of the protocol is that the underlying network is not reliable. Adding more layers atop TCP/IP only exacerbates the problem of latency.}

% Label
\label{pgfId-10764}

\item{Sloppy Object Model : Perhaps the worst aspect of the RMI system is its sloppy object model. Any class that is going to be used to create remote objects must inherit from one of Java’s base classes, such as UnicastRemoteObject . This may not seem like a problem at first, but presents a great deal of difficulty if the class being served is actually a subclass of another class already. Unlike the Threads classes, which also have companion interfaces that can be implemented, RMI forces you to waste inheritance from a class that has no perceptibly useful functionality. This has also been discussed in a paper written by one of the authors.}

% Label
\label{pgfId-10765}

\end{itemize}

% Label
\label{pgfId-10771}
There are more reasons; however, this list should be enough for anyone to think twice before trying to use RMI for an application that was never intended. RMI looks a little too much like a client-server paradigm, and what we need is a more peer-oriented paradigm.
\par

\subsubsection{GMI: Goals and Design Overview}

% Label
\label{pgfId-12732}

% Label
\label{pgfId-10776}
GMI was thus created not as an alternative to RMI, but rather as a building block for building a peer-oriented communication system. It was also designed with extensibility in mind. The basic design of GMI consists of a very lean set of classes:
\par

\begin{itemize}

\item{CallMessage : This is an extension of the Message class. The key difference between the CallMessage and a Message is the ability to encode and decode. These functions can be useful to pack or unpack data structures that are sent as messages.}

% Label
\label{pgfId-10780}

\item{Callable : This is an interface that can be implemented so an object can receive messages. The concept of Callable is very similar to the Deliverable concept presented in the discussion of SMA, but one level up.}

% Label
\label{pgfId-10781}

\item{RemoteCallServer : This is a class that can be used to receive remote calls. The RemoteCallServer provides an API very similar to Java’s naming framework (the interface to the rmiregistry). The difference here is that the RemoteCallServer also doubles as a registry for finding objects by name.}

% Label
\label{pgfId-10782}

\item{RemoteCallClient : This is a class used to make remote calls.}

% Label
\label{pgfId-10783}

\end{itemize}

\subsubsection{Callable : An Interface for Accepting Communication}

% Label
\label{pgfId-10683}

% Label
\label{pgfId-12719}
The notion of a
\texttt{Callable}
bears many similarities to the
\texttt{MessageRecipient}
presented in the SMA classes from the previous chapter. The callable notion refers to any object that can be called (remotely) with a
\texttt{CallMessage}
object.
\par

% Label
\label{pgfId-12725}

\par

	\begin{verbatim}
	

package jhpc.gmi;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

import java.io.*;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

public interface Callable {
	\end{verbatim}
	
	\begin{verbatim}
	

    Serializable call(CallMessage message) throws Exception;
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
\subsubsection{}

% Label
\label{pgfId-12738}

\subsubsection{CallMessage: An Abstract Class for Marshalling and Unmarshalling!}

% Label
\label{pgfId-12739}

% Label
\label{pgfId-12729}
The
\texttt{CallMessage}
class is used to package parameters for a remote communication. It is usually subclassed. The
\texttt{CallMessage}
class provides a single instance variable (target) that is used to specify the remote invocation target. In GMI, the notion of an invocation target is a character string that uniquely represents the name of an object on the server side. A similar idea is found in Java’s RMI with the addition of a special URL syntax. (RMI objects are referred to with a string of the form rmi://host:port/object-name.) We have not chosen this approach in GMI, since a client holds a reference to a remote call server (i.e., the host-port combintation is encapsulated in a connection), and thus a particular name can only refer to an object at a specific remote location. As we will demonstrate shortly, this framework is very transparent and easy to understand and minimizes much unwanted complexity (and overhead) that is found in RMI itself. Consider the following code:
\par

	\begin{verbatim}
	

package jhpc.gmi;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

import java.io.*;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

public abstract class CallMessage implements Serializable {
	\end{verbatim}
	
	\begin{verbatim}
	

    protected String target;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public CallMessage(String target) {
	\end{verbatim}
	
	\begin{verbatim}
	

        this.target = target;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void setTarget(String target) {
	\end{verbatim}
	
	\begin{verbatim}
	

        this.target = target;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public final String getTarget() {
	\end{verbatim}
	
	\begin{verbatim}
	

        return target;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-10876}
A couple of points are in order about the
\texttt{CallMessage}
:
\par

\begin{enumerate}

\item{Serializable : Any message must be serializable. Java object serialization is provided in the ObjectInputStream and ObjectOutputStream classes, which have the capability of reading and writing objects, respectively. We have not covered serialization in this book (again leaving the discussion to other books that already cover this material in detail), but make use of it only for exchanging objects between the client and the server (and vice versa).}

\item{CallMessage(String target) : All subclasses must call this constructor to ensure that the target object name field is properly initialized. It is permitted to have a null target object (acceptable only when a message is a reply from a remote call).}

\end{enumerate}

\subsubsection{RemoteCallServer}

% Label
\label{pgfId-10685}

% Label
\label{pgfId-12745}
Similar to the
\texttt{MessageServer}
class found in the SMA framework from the networking chapter, GMI provides similar classes with different names:
\texttt{RemoteCallServer}
(to provide basic registration facilities),
\texttt{RemoteCallServerDispatcher}
(to actually service the remote call), and
\texttt{RemoteCallClient}
(to allow clients to reach a
\texttt{RemoteServer}
to make calls).
\par

% Label
\label{pgfId-12746}
The
\texttt{RemoteCallServer}
bears some similarities to RMI. There are two sets of methods: registration of
\texttt{Callable}
instances and serving remote calls.
\par

% Label
\label{pgfId-12747}
Let us first consider the aspects of the
\texttt{RemoteCallServer}
that pertain to registration:
\par

\begin{enumerate}

\item{registeredObjects : All registrations are maintained in a Java Hashtable object. The key is simply a string that represents a user-defined name for contacting a Callable object remotely; the value is the Callable object itself.}

\item{bind() : This method is used to bind a given Callable instance to a user-defined name. This method simply uses the underlying Hashtable put() method to store the association in the Hashtable .}

\item{unbind() : This method allows a previous binding (done with bind() ) to be remoted from the Hashtable of registered objects.}

\item{lookup() : This method looks up a previously defined binding.}

\end{enumerate}

% Label
\label{pgfId-12758}
Remember that this is not RMI! These functions are all intended to be called on the server side of the picture only. Clients are fully insulated from all details of registration and simply refer to remote objects by specifying the target object name in the
\texttt{CallMessage}
. We have chosen names similar to those found in the naming framework of RMI simply to ease the transition to GMI and not with the purpose of maintaining (or promising) any degree of compatibility.
\par

% Label
\label{pgfId-12765}
Consider the following code:
\par

% Label
\label{pgfId-13990}

\par

	\begin{verbatim}
	

package jhpc.gmi;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

import java.net.*;
	\end{verbatim}
	
	\begin{verbatim}
	

import java.io.*;
	\end{verbatim}
	
	\begin{verbatim}
	

import java.util.*;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

public class RemoteCallServer extends Thread {
	\end{verbatim}
	
	\begin{verbatim}
	

    private Hashtable registeredObjects = new Hashtable();
	\end{verbatim}
	
	\begin{verbatim}
	

    private ServerSocket callListener;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public RemoteCallServer(int port) throws IOException {
	\end{verbatim}
	
	\begin{verbatim}
	

        callListener = new ServerSocket(port);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public synchronized void bind(String target, 
	\end{verbatim}
	
	\begin{verbatim}
	

                                  Callable callable) {
	\end{verbatim}
	
	\begin{verbatim}
	

        registeredObjects.put(target, callable);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public synchronized void unbind(String target) {
	\end{verbatim}
	
	\begin{verbatim}
	

        registeredObjects.remove(target);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public synchronized Callable lookup(String target) {
	\end{verbatim}
	
	\begin{verbatim}
	

        return (Callable) registeredObjects.get(target);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void run() {
	\end{verbatim}
	
	\begin{verbatim}
	

        while (true) {
	\end{verbatim}
	
	\begin{verbatim}
	

            try {
	\end{verbatim}
	
	\begin{verbatim}
	

                Socket s=callListener.accept();
	\end{verbatim}
	
	\begin{verbatim}
	

                RemoteCallServerDispatcher csd = 
	\end{verbatim}
	
	\begin{verbatim}
	

                   new RemoteCallServerDispatcher(this, s);
	\end{verbatim}
	
	\begin{verbatim}
	

                csd.setDaemon(false);
	\end{verbatim}
	
	\begin{verbatim}
	

                csd.start();
	\end{verbatim}
	
	\begin{verbatim}
	

            } catch(Exception e) { System.out.println(e); }
	\end{verbatim}
	
	\begin{verbatim}
	

           }
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-12766}
The rest of what you see in this class is dedicated to “being a server.” This code is very similar to what is found in the SMA classes. This code is intended to be run as a thread. The
\texttt{run()}
method contains the familiar server loop. When a connection is accepted, a
\texttt{RemoteCallServerDispatcher}
instance is created to handle the incoming call. It is in this class where there are notable differences from the comparable SMA class
\texttt{MessageServer}
. The most important detail to notice in the server loop is that a reference to the
\texttt{RemoteCallServer}
instance
\texttt{this}
is passed to the
\texttt{RemoteCallServerDispatcher}
instance, thus making it possible for the various dispatcher instances to look up callables to perform the remote call.
\par

\subsubsection{RemoteCallServerDispatcher}

% Label
\label{pgfId-10941}

% Label
\label{pgfId-12775}
The
\texttt{RemoteCallServerDispatcher}
class is similar to the
\texttt{MessageServerDispatcher}
class of SMA. The notable difference is that
\texttt{DataInputStream}
and
\texttt{DataOutputStream}
have been replaced with
\texttt{ObjectInputStream}
and
\texttt{ObjectOutputStream}
classes, which allow arbitrary Java objects to be exchanged between the
\texttt{RemoteCallClient}
and itself.
\ref{#id(pgfId-12783)}[MISSING HREF]

\par

% Label
\label{pgfId-12781}
The constructor initializes the
\texttt{in}
and
\texttt{out}
variables as done in the
\texttt{MessageServerDispatcher}
class, this time initializing the
\texttt{ObjectInputStream}
and
\texttt{ObjectOutputStream}
from the
\texttt{InputStream}
and
\texttt{OutputStream}
, respectively, associated with the incoming socket:
\par

% Label
\label{pgfId-12801}

\par

	\begin{verbatim}
	

package jhpc.gmi;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

import java.io.*;
	\end{verbatim}
	
	\begin{verbatim}
	

import java.net.*;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

public class RemoteCallServerDispatcher extends Thread {
	\end{verbatim}
	
	\begin{verbatim}
	

    RemoteCallServer callServer;
	\end{verbatim}
	
	\begin{verbatim}
	

    Socket socket;
	\end{verbatim}
	
	\begin{verbatim}
	

    ObjectInputStream in;
	\end{verbatim}
	
	\begin{verbatim}
	

    ObjectOutputStream out;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public RemoteCallServerDispatcher(RemoteCallServer callServer,
 		Socket socket)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws IOException {
	\end{verbatim}
	
	\begin{verbatim}
	

        this.callServer = callServer;
	\end{verbatim}
	
	\begin{verbatim}
	

        this.socket = socket;
	\end{verbatim}
	
	\begin{verbatim}
	

        InputStream inRaw = socket.getInputStream();
	\end{verbatim}
	
	\begin{verbatim}
	

        this.in = new ObjectInputStream(inRaw);
	\end{verbatim}
	
	\begin{verbatim}
	

        OutputStream outRaw = socket.getOutputStream();
	\end{verbatim}
	
	\begin{verbatim}
	

        this.out = new ObjectOutputStream(outRaw);     }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void run() {
	\end{verbatim}
	
	\begin{verbatim}
	

        CallMessage message = null;
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            while (true) {
	\end{verbatim}
	
	\begin{verbatim}
	

                message = (CallMessage)in.readObject();
	\end{verbatim}
	
	\begin{verbatim}
	

                if (message instanceof Goodbye) {
	\end{verbatim}
	
	\begin{verbatim}
	

                    out.writeObject(message);
	\end{verbatim}
	
	\begin{verbatim}
	

                    out.close();
	\end{verbatim}
	
	\begin{verbatim}
	

                    return;
	\end{verbatim}
	
	\begin{verbatim}
	

                }
	\end{verbatim}
	
	\begin{verbatim}
	

                Callable callTarget =
	\end{verbatim}
	
	\begin{verbatim}
	

                  callServer.lookup(message.getTarget());
	\end{verbatim}
	
	\begin{verbatim}
	

                Serializable result;
	\end{verbatim}
	
	\begin{verbatim}
	

                if (callTarget != null)
	\end{verbatim}
	
	\begin{verbatim}
	

                    result = callTarget.call(message);
	\end{verbatim}
	
	\begin{verbatim}
	

                else
	\end{verbatim}
	
	\begin{verbatim}
	

                    result = null;
	\end{verbatim}
	
	\begin{verbatim}
	

                out.writeObject(result);
	\end{verbatim}
	
	\begin{verbatim}
	

                out.flush();
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch (EOFException e1) {
	\end{verbatim}
	
	\begin{verbatim}
	

            try {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.err.println(e1);
	\end{verbatim}
	
	\begin{verbatim}
	

                out.close();
	\end{verbatim}
	
	\begin{verbatim}
	

                socket.close();
	\end{verbatim}
	
	\begin{verbatim}
	

                e1.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            } catch (Exception e2) {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.err.println(e2);
	\end{verbatim}
	
	\begin{verbatim}
	

                e2.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch (Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.err.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

       }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-11003}
The
\texttt{run()}
method uses the
\texttt{readObject()}
method to read a
\texttt{CallMessage}
object from the underlying stream. We know for a fact that an object of type
\texttt{CallMessage}
or subclass thereof is the only type of object that can be read from the underlying stream. (You can verify this by studying the
\texttt{RemoteCallClient}
code in the next section, but trust us for the time being!) The following steps are done upon receiving a
\texttt{CallMessage}
(
\texttt{message}
):
\par

\begin{enumerate}

\item{The message is first checked to determine whether it is the reserved Goodbye message. The Goodbye message (which is a subclass of CallMessage ) exists to enable the client to politely (as opposed to rudely) go away. Connections with the client are persistent and thus only go away when either (a) the client sends the Goodbye message, or (b) an exception occurs. If the Goodbye message is received, the connection with the client is gracefully closed, and the dispatcher thread exits gracefully as well. Otherwise, continue to step 2.}

\item{The message is then examined for the target object name. The target object name is not supposed to be null; however, if it is, the message simply cannot be delivered, and null is returned. The only condition by which null is returned is when no invocation takes place. The call server (i.e., the RemoteCallServer object that created this dispatch thread, or, more appropriately, the parent) is contacted to actually perform the call. It is entirely possible that the target name refers to an object that does not exist; however, this also results in a null return.}

\item{Once the invocation is completed, a reply is returned. This reply must be sent to the RemoteCallClient object, using the writeObject() method. The flush() method is called every time an object is written to an ObjectOutputStream . This is, in general, necessary, because Java streams are buffered. Failing to flush() may result in the opposite end of this connection (a RemoteCallClient object) being blocked indefinitely on a readObject() call.}

\end{enumerate}

% Label
\label{pgfId-12814}
Thus, the
\texttt{RemoteCallServerDispatcher}
code is in many respects identical (in principle) to the
\texttt{MessageServerDispatcher}
code, with the notable difference being that serializable objects are involved. From the standpoint of the server side, the
\texttt{RemoteallServerDispatcher}
does virtually all of the work, except for managing the remote objects and actually performing the remote calls (both of which are left to the
\texttt{RemoteCallServer}
that created the
\texttt{RemoteCallServerDispatcher}
instance).
\par

\subsubsection{RemoteCallClient}

% Label
\label{pgfId-10686}

% Label
\label{pgfId-12817}
The
\texttt{RemoteCallClient}
class is essentially the user interface that allows clients to easily send
\texttt{CallMessage}
objects to a remote object. An initial connection must first be made to a
\texttt{RemoteCallServer}
. The constructor for this class, much like the SMA
\texttt{MessageClient}
, allows a host and port combination to be specified. A socket is opened, and (as in the
\texttt{RemoteCallServerDispatcher}
)
\texttt{ObjectInputStream}
and
\texttt{ObjectOutputStream}
references are obtained for communication with the server.
\par

% Label
\label{pgfId-12818}
The work done in the
\texttt{call()}
method is very similar to the work done by the
\texttt{RemoteCallServerDispatcher}
server loop shown earlier. The parameter to the
\texttt{call()}
method is a single
\texttt{CallMessage}
instance.
\ref{#id(pgfId-12820)}[MISSING HREF]

\par

	\begin{verbatim}
	

package jhpc.gmi;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

import java.io.*;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

import java.net.*;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

public class RemoteCallClient extends Thread {
	\end{verbatim}
	
	\begin{verbatim}
	

    Socket socket;
	\end{verbatim}
	
	\begin{verbatim}
	

    ObjectOutputStream out;
	\end{verbatim}
	
	\begin{verbatim}
	

    ObjectInputStream in;
	\end{verbatim}
	
	\begin{verbatim}
	

    OutputStream debug = null;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public RemoteCallClient(String host, int port)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws IOException {
	\end{verbatim}
	
	\begin{verbatim}
	

        socket = new Socket(host, port);
	\end{verbatim}
	
	\begin{verbatim}
	

        out = new ObjectOutputStream(socket.getOutputStream());
	\end{verbatim}
	
	\begin{verbatim}
	

        in = new ObjectInputStream(socket.getInputStream());    
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object call(CallMessage message) {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            out.writeObject(message);
	\end{verbatim}
	
	\begin{verbatim}
	

            out.flush();
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.err.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            return null;
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        Object result;
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            result = in.readObject();
	\end{verbatim}
	
	\begin{verbatim}
	

            return result;
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.err.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            return null;
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

   
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object call(String altTarget, CallMessage message) {
	\end{verbatim}
	
	\begin{verbatim}
	

        message.setTarget(altTarget);
	\end{verbatim}
	
	\begin{verbatim}
	

        return call(message);
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void disconnect() {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            out.writeObject(new Goodbye());
	\end{verbatim}
	
	\begin{verbatim}
	

            out.flush();
	\end{verbatim}
	
	\begin{verbatim}
	

            Object result = in.readObject();
	\end{verbatim}
	
	\begin{verbatim}
	

            out.close();
	\end{verbatim}
	
	\begin{verbatim}
	

            socket.close();
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.err.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-11089}
The
\texttt{call()}
method takes the
\texttt{CallMessage}
object (which is known to be of type
\texttt{Serializable}
) and writes it to the network. Then, the reply is read from the server, which must also be a
\texttt{CallMessage}
. This reply is then returned as the result of
\texttt{call()}
.
\par

% Label
\label{pgfId-12823}
GMI is intended to be a simple remote procedure-calling framework. To be fair, let us say that there are a good number of things we have not done that you would find in the RMI framework from Sun. These details are summarized as follows:
\par

\begin{enumerate}

\item{No remote exceptions: This version of GMI does not handle remote exceptions. It is rather trivial to incorporate this enhancement, since it is merely a matter of reserving space for an Exception reference in CallMessage . An enhanced version of GMI can be downloaded from the course Web site.}

\item{No stubs and skeletons: Stubs and skeletons have been completely eliminated from this design. This is because we are less concerned with call transparency (i.e., the appearance that a remote call is just like calling a local function) than the potential for getting good performance. Supporting call transparency has the (undesirable) property of adding layers, which simply is not efficient. Since we are going to be adding a layer to GMI ( Memo ), the intent is to keep the number of layers to a minimum, while maintaining a sound design from an engineering and computing perspective.}

\item{No forced subclassing: Classes used to make remote objects in RMI must subclass UnicastRemoteObject, and all methods must throw RemoteException . This is extremely cumbersome and almost makes the call transparency of RMI not worth the trouble, since you must be aware of so many details of the typing system in order to get the results. With GMI, any class can easily be made remote simply by implementing the Callable interface, providing a call() method, and providing an appropriate subclass of CallMessage to communicate to and from the remote object.}

\item{Calls are not synchronized: When you open a connection between client and server, the calls are not synchronized. This capability has been provided strictly for the implementation of our higher level message passing systems, which require the ability to block (remotely). This means that calls must be explicitly locked that need to be atomic. Our implementation fully protects you on the server side, since a separate dispatcher is created to service each client, so you only need be concerned when creating client side threads that are all sharing a connection to a common RemoteCallServer . An alternative is to simply make separate connections to the RemoteCallServer using multiple RemoteCallClient instances (i.e., one instance of RemoteCallClient per thread).}

\end{enumerate}

\section{Memo: A Remote Interface to SharedTableOfQueues}

% Label
\label{pgfId-10669}

% Label
\label{63067}

% Label
\label{pgfId-12844}
In Chapter 9, we presented the shared-table-of-queues abstraction, which represents a major building block of a coordination system. We created the shared table of (unordered) queues after observing that systems such as Linda (from Yale University) and Java Spaces are really nothing more than extensions of this fundamental principle that has been used in computing since the early days of operating systems. Linda and Java Spaces are both examples of tuple spaces.
\par

% Label
\label{pgfId-12846}
The Memo system is an implementation of a tuple space; however, the concept of a tuple has been superseded by an object, which is a much more general concept than a tuple.
\par

\subsubsection{Design}

% Label
\label{pgfId-10687}

% Label
\label{pgfId-12852}
The design of
\texttt{Memo}
is relatively straightforward. The GMI classes presented in the previous section are used to provide a remote interface to the
\texttt{SharedTableOfQueues}
class presented earlier. The following is a summary of the different key classes and their purpose:
\par

\begin{enumerate}

\item{MemoMessage : This abstract class (derived from CallMessage ) is used to request one of the various remote methods from the SharedTableOfQueues class. Since it is a subclass of CallMessage , a target object name must be specified. The additional method go(SharedTableOfQueues stoq) that allows the operation to be performed once the MemoServer has control of the MemoMessage is provided.}

\item{MemoServer : This class implements the Callable interface. It is used to accept the various instances of a subclass of MemoMessage (which is a subclass of CallMessage ). When a given MemoMessage is received, an appropriate action will take place on the SharedTableOfQueues instance.}

\item{MemoClient : This class is used to provide the same methods for the client that are available in the SharedTableOfQueues class. Every method in this class has the same general implementation. The parameters are packed into one of the various MemoMessage subclass instances and sent to a remote MemoServer . Then, the result of the remote call is obtained as passed back to the client.}

\end{enumerate}

% Label
\label{pgfId-12857}
In the interest of conciseness, we will only discuss a few of the methods. As our examples in this chapter only make use of the basic methods (the
\texttt{put()}
and
\texttt{get()}
methods), we shall only discuss these two here and leave the rest for self-study (and a future book, an unresolved forward reference).
\par

% Label
\label{pgfId-12864}
The following code shows the
\texttt{MemoMessage}
class:
\par

	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

public abstract class MemoMessage extends CallMessage {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public MemoMessage(String target) {
	\end{verbatim}
	
	\begin{verbatim}
	

       super(target);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public abstract Serializable go(SharedTableOfQueues stoq)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-12870}
This class is marked abstract because instances of it are never created. The difference between
\texttt{CallMessage}
and
\texttt{MemoMessage}
is simply the
\texttt{go()}
method. The
\texttt{go()}
method must be overridden in the subclass to perform the operation on a remote
\texttt{SharedTableOfQueues}
(stoq).
\par

% Label
\label{pgfId-12900}
The
\texttt{MemoGet}
subclass of
\texttt{MemoMessage}
is as follows:
\par

	\begin{verbatim}
	

class MemoGet extends MemoMessage {
	\end{verbatim}
	
	\begin{verbatim}
	

    Serializable key;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public MemoGet(String target, Serializable key) {
	\end{verbatim}
	
	\begin{verbatim}
	

      super(target);
	\end{verbatim}
	
	\begin{verbatim}
	

      this.key=key; 
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Serializable go(SharedTableOfQueues stoq)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	

        return (Serializable) stoq.get(key);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-12897}
This class shows the essence of how GMI programming is done in practice. Typically, a constructor is provided that initializes the target object name and whatever parameters would normally be required to perform the remote call (thinking in RPC or RMI terms). Here the parameter that is needed is key. Why? Recall the method header from the
\texttt{SharedTableOfQueues}
class:
\par

	\begin{verbatim}
	

	public Object get(Object key) throws InterruptedException
	\end{verbatim}
	
% Label
\label{pgfId-12910}
In the constructor for
\texttt{MemoGet}
, we translated
\texttt{key}
from
\texttt{Object}
to
\texttt{Serializable}
. This was to ensure that the message and any object references it contains are
\texttt{Serializable}
. This is not required, but rather is a matter of personal preference. It would have been perfectly acceptable to pass an
\texttt{Object}
as the parameter and allow an exception to occur if the
\texttt{key}
in fact proved not to be
\texttt{Serializable}
. As there was no loss of generality, we chose to make the interface safe from the end-user perspective.
\par

% Label
\label{pgfId-12957}
Let us now consider the
\texttt{MemoPut}
message, which is used to access the
\texttt{SharedTableOfQueues}

\texttt{put()}
function. Recall that the
\texttt{put()}
method has the following form:
\par

	\begin{verbatim}
	

	public void put(Object key, Object value)
	\end{verbatim}
	
% Label
\label{pgfId-12958}
The following code shows the
\texttt{MemoPut}
class:
\par

% Label
\label{pgfId-12959}

\par

	\begin{verbatim}
	

class MemoPut extends MemoMessage {
	\end{verbatim}
	
	\begin{verbatim}
	

    Serializable key, value;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public MemoPut(String target, Serializable key, 
		Serializable value){
	\end{verbatim}
	
	\begin{verbatim}
	

      super(target);
	\end{verbatim}
	
	\begin{verbatim}
	

      this.key=key;
	\end{verbatim}
	
	\begin{verbatim}
	

      this.value = value;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Serializable go(SharedTableOfQueues stoq) {
	\end{verbatim}
	
	\begin{verbatim}
	

      stoq.put(key,value);
	\end{verbatim}
	
	\begin{verbatim}
	

      return new Ok(true);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-12915}
In this case, the constructor now has two parameters in addition to the target object name:
\texttt{key}
and
\texttt{value}
. Again, as a matter of preference and concern for the end user, we have chosen to make both of these parameters
\texttt{Serializable}
.
\par

% Label
\label{pgfId-12960}
The operation is performed on the actual
\texttt{SharedTableOfQueues}
in the
\texttt{go()}
method. When writing remote interfaces to
\texttt{void}
methods, it is necessary to return a value. GMI provides a class for general-purpose acknowledgments (
\texttt{Ok}
) that can be set true or false to indicate success or failure. Here, we unconditionally indicate that the remote operation was successful (which will only occur when there is no exception caused by the
\texttt{put()}
call).
\par

% Label
\label{pgfId-13103}
Let us now consider the case of the
\texttt{SharedTableOfQueues runDelayed()}
method, which allows a thread to perform a computation (asynchronously) that, when completed, leaves a result in the
\texttt{SharedTableOfQueues}
for subsequent retrieval.
\par

% Label
\label{pgfId-13104}
The
\texttt{runDelayed()}
method has the following form:
\par

	\begin{verbatim}
	

	public void runDelayed(Object key,Runnable r)
	\end{verbatim}
	
% Label
\label{pgfId-13107}
This is parsed as “start the
\texttt{Runnable}

\texttt{r}
remotely as a thread, and leave the result behind as if
\texttt{MemoPut(key, r)}
had been performed.”
\par

% Label
\label{pgfId-13108}
The following code shows the MemoRunDelayed class:
\par

	\begin{verbatim}
	

class MemoRunDelayed extends MemoMessage implements Runnable {
	\end{verbatim}
	
	\begin{verbatim}
	

    Serializable key;
	\end{verbatim}
	
	\begin{verbatim}
	

    Serializable runnable;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public MemoRunDelayed(String target, Serializable key,
	\end{verbatim}
	
	\begin{verbatim}
	

                          Serializable runnable) {
	\end{verbatim}
	
	\begin{verbatim}
	

      super(target);
	\end{verbatim}
	
	\begin{verbatim}
	

      this.key = key;
	\end{verbatim}
	
	\begin{verbatim}
	

      this.runnable = runnable;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Serializable go(SharedTableOfQueues stoq) {
	\end{verbatim}
	
	\begin{verbatim}
	

      stoq.runDelayed(key, this);
	\end{verbatim}
	
	\begin{verbatim}
	

      return new Ok(true);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void run(){
	\end{verbatim}
	
	\begin{verbatim}
	

      if (runnable instanceof Runnable) {
	\end{verbatim}
	
	\begin{verbatim}
	

         Runnable r = (Runnable)runnable;
	\end{verbatim}
	
	\begin{verbatim}
	

         r.run();
	\end{verbatim}
	
	\begin{verbatim}
	

      } else {
	\end{verbatim}
	
	\begin{verbatim}
	

         // Strictly speaking, an exception should be thrown here.
	\end{verbatim}
	
	\begin{verbatim}
	

      }
	\end{verbatim}
	
	\begin{verbatim}
	

   }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-13114}
This class shows some of the problems of working with interfaces (something you must know how to do, regardless of whether you use GMI, RMI, or CORBA). We want the ability to guarantee that both parameters (
\texttt{key}
and
\texttt{r}
) are
\texttt{Serializable}
. We also want the ability to guarantee that the parameter
\texttt{r}
is
\texttt{Runnable}
.
\ref{#id(pgfId-13116)}[MISSING HREF]
Ultimately, we decided in favor of enforcing the
\texttt{Serializable}
interface (which, if not checked, results in a great deal of trouble when working with object streams) and performing a run-time check just as we are about to run the
\texttt{Runnable}
.
\par

% Label
\label{pgfId-13118}
Notice that the
\texttt{go()}
method simply calls the
\texttt{runDelayed()}
method of the
\texttt{SharedTableOfQueues}
class and returns an
\texttt{Ok}
message immediately. The
\texttt{runDelayed()}
method, in turn, creates a
\texttt{Thread}
instance from this message, hence the presence of the
\texttt{run()}
method. This
\texttt{run()}
method is simply a delegate that dispatches the actual
\texttt{Runnable r}
that was passed as part of the
\texttt{MemoRunDelayed}
message.
\par

% Label
\label{pgfId-13122}
The remaining
\texttt{MemoMessage}
subclasses are all fairly straightforward. Here, we have presented the two easiest to follow (
\texttt{MemoGet}
and
\texttt{MemoPut}
) and the most difficult (
\texttt{MemoRunDelayed}
). All code is provided on the book CD and Web site.
\par

% Label
\label{pgfId-13132}
The key thing to understand is that the
\texttt{go()}
method in the
\texttt{MemoMessage}
basically is where the remote operation is performed. This allows the messages themselves to play a role in carrying out the remote operation. It is for this reason that the
\texttt{MemoServer}
code will be fairly straightforward to understand, since the
\texttt{MemoServer}
instance simply takes a message that has been received and instructs it to perform the operation directly on a
\texttt{SharedTableOfQueues}
object.
\par

\subsubsection{MemoServer}

% Label
\label{pgfId-10690}

% Label
\label{pgfId-13126}
Not surprisingly, the
\texttt{MemoServer}
code is straightforward and almost requires no additional information to be said about it. Nonetheless, we do offer a few words to tie a few loose ends together. The code is as follows:
\par

% Label
\label{pgfId-13133}

\par

	\begin{verbatim}
	

public class MemoServer implements Callable {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    SharedTableOfQueues stoq = new SharedTableOfQueues();
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Serializable call(CallMessage message)
	\end{verbatim}
	
	\begin{verbatim}
	

        throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        if (message instanceof MemoMessage) {
	\end{verbatim}
	
	\begin{verbatim}
	

            MemoMessage mm = (MemoMessage) message;
	\end{verbatim}
	
	\begin{verbatim}
	

            Serializable reply = mm.go(stoq);
	\end{verbatim}
	
	\begin{verbatim}
	

            return reply;
	\end{verbatim}
	
	\begin{verbatim}
	

 
	\end{verbatim}
	
	\begin{verbatim}
	

        } else {
	\end{verbatim}
	
	\begin{verbatim}
	

            return new Ok(false);
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

   }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-13136}

\texttt{MemoServer}
is a class that implements
\texttt{Callable}
, which is required of any class that wants to act in a remote setting. It simply creates the
\texttt{SharedTableOfQueues}
instance (which will be used remotely) and provides a
\texttt{call()}
method. The code for performing the call on the server side is very straightforward. The message is checked to ensure that it is a
\texttt{MemoMessage}
(or a subclass). The downcast is performed, and the
\texttt{MemoMessage}
itself performs the operation on the
\texttt{SharedTableOfQueues}
instances
\texttt{stoq}
. In the unlikely event that the wrong type of message gets passed to the call, the general-purpose acknowledgment message
\texttt{Ok}
is returned with a status of false. This will, in fact, never occur.
\par

% Label
\label{pgfId-13140}
A few words are in order about RPC in a parallel context. First, note that the
\texttt{call()}
method itself is not synchronized. Call synchronization is optional. If you need pure RPC semantics and have no need for the remote calls to block indefinitely (which we do in the case of the
\texttt{put()}
and
\texttt{get()}
methods), you should use the synchronized keyword accordingly.
\par

% Label
\label{pgfId-13148}
Note that the
\texttt{MemoServer}
class, despite having the word “server” in its name, is not in fact the server. GMI provides
\texttt{RemoteCallServer}
, which contains the actual server loop. A
\texttt{MemoServer}
is created (trivially) by creating a
\texttt{RemoteCallServer}
instance and binding a name through which the
\texttt{MemoServer}
instance will be contacted:
\par

	\begin{verbatim}
	

	RemoteCallServer server = new RemoteCallServer(port);
	\end{verbatim}
	
	\begin{verbatim}
	

	server.bind(“memo”, new MemoServer());
	\end{verbatim}
	
% Label
\label{pgfId-13155}
Any application may create a
\texttt{MemoServer}
simply by adding the preceding two lines. We provide an example server in the
\texttt{MemoServer}
class as an inner class.
\par

\subsubsection{MemoClient}

% Label
\label{pgfId-10691}

% Label
\label{pgfId-13156}
The
\texttt{MemoClient}
is provided as a convenience class, so users of the
\texttt{Memo}
system do not need to make direct use of the various
\texttt{MemoMessage}
subclasses to perform
\texttt{Memo}
operations. Thus, users of the
\texttt{Memo}
system are completely isolated from the underlying communication system and simply make use of functions from the familiar
\texttt{SharedTableOfQueues}
class.
\par

% Label
\label{pgfId-13161}
The code for
\texttt{MemoClient}
is as follows:
\par

	\begin{verbatim}
	

public class MemoClient {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    RemoteCallClient rc;
	\end{verbatim}
	
	\begin{verbatim}
	

    String target;
	\end{verbatim}
	
	\begin{verbatim}
	

    String host;
	\end{verbatim}
	
	\begin{verbatim}
	

    int port;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public MemoClient(String host, int port, String target)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	

        this.host = host;
	\end{verbatim}
	
	\begin{verbatim}
	

        this.port = port;
	\end{verbatim}
	
	\begin{verbatim}
	

        this.rc = new RemoteCallClient(host,port);
	\end{verbatim}
	
	\begin{verbatim}
	

        this.target = target;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void disconnect() {
	\end{verbatim}
	
	\begin{verbatim}
	

        rc.disconnect();
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void goodbye() {
	\end{verbatim}
	
	\begin{verbatim}
	

        rc.disconnect();
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public void setTarget(String target) {
	\end{verbatim}
	
	\begin{verbatim}
	

        this.target = target;
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object get(Serializable key) 
	\end{verbatim}
	
	\begin{verbatim}
	

      throws InterruptedException {
	\end{verbatim}
	
	\begin{verbatim}
	

        MemoGet mg = new MemoGet(target, key);
	\end{verbatim}
	
	\begin{verbatim}
	

        return rc.call(mg);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object put(Serializable key, Serializable value) {
	\end{verbatim}
	
	\begin{verbatim}
	

        MemoPut mp = new MemoPut(target, key, value);
	\end{verbatim}
	
	\begin{verbatim}
	

        return rc.call(mp);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object getCopy(Serializable key)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws InterruptedException {
	\end{verbatim}
	
	\begin{verbatim}
	

        MemoGetCopy mgc = new MemoGetCopy(target, key);
	\end{verbatim}
	
	\begin{verbatim}
	

        return rc.call(mgc);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object getCopySkip(Serializable key) {
	\end{verbatim}
	
	\begin{verbatim}
	

        MemoGetCopySkip mgcs = new MemoGetCopySkip(target, key);
	\end{verbatim}
	
	\begin{verbatim}
	

        return rc.call(mgcs);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object getSkip(Serializable key)  {
	\end{verbatim}
	
	\begin{verbatim}
	

        MemoGetSkip mgs = new MemoGetSkip(target, key);
	\end{verbatim}
	
	\begin{verbatim}
	

        return rc.call(mgs);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public Object runDelayed(Serializable key, Runnable r)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	

        if (r instanceof Serializable) {
	\end{verbatim}
	
	\begin{verbatim}
	

            Serializable rs = (Serializable) r;
	\end{verbatim}
	
	\begin{verbatim}
	

            MemoRunDelayed mrd = new MemoRunDelayed(target, key, rs);
	\end{verbatim}
	
	\begin{verbatim}
	

            return rc.call(mrd);
	\end{verbatim}
	
	\begin{verbatim}
	

        } else throw new Exception(“r not Serializable”);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-11328}
The code should be fairly straightforward to understand. To create this class, we essentially copied all of the methods from the
\texttt{SharedTableOfQueues}
class and added the following:
\par

\begin{enumerate}

\item{A constructor to initiate the remote connection via a RemoteCallClient object. The only aspect that is exposed to end users is the target object name. This is necessary to allow for the possibility of creating an arbitrary number of MemoServer instances and allowing clients the freedom to connect to them.}

\item{The various methods all correspond to existing SharedTableOfQueues methods, except for the goodbye() and disconnect() methods, which are used to politely disconnect from the GMI RemoteCallServer instance. For the most part, every method simply packages the parameters into a MemoMessage (or subclass thereof) and then issues a call via the RemoteCallServer .}

\end{enumerate}

% Label
\label{pgfId-13183}
The
\texttt{MemoClient}
provides a glimpse for how the GMI system could eventually become a transparent remote procedure-calling system, similar to RMI; however, this is well beyond the scope of this book. Our purpose has been to use the notion of remote procedure calling as a means to an end and not the end result itself. The
\texttt{Memo}
system is much more well-suited to thinking about parallel and distributed programming (where more than two entities are involved) than remote procedure calls (and RMI), and the rest of this section is dedicated to demonstrating the applicability of
\texttt{Memo}
to writing a few parallel codes.
\par

\section{Vector Inner Product}

% Label
\label{pgfId-11331}

% Label
\label{21393}

% Label
\label{pgfId-11355}
The first code example we shall consider is the vector inner product. The intention of this example is to show the basic capabilities that are possible with
\texttt{Memo}
. The vector inner product is not considered a computational grand challenge. Nonetheless, it is a good pedagogical example of how many interesting parallel problems are decomposed and solved using multiple processes running on one or more computers.
\par

% Label
\label{pgfId-13173}
The idea of the vector inner product is very simple. Two vectors (arrays) of floating-point values are defined --
\emph{v}
and
\emph{w}
, with values
\emph{v}
=(
\emph{v}
0,
\emph{v}
1, ...,
\emph{vN}
-1) and
\emph{w}
=(
\emph{w}
0,
\emph{w}
1, ...,
\emph{wN}
-1). The inner product is computed by summing up the products of all corresponding elements in vectors
\emph{v}
and
\emph{w}
:
\par

% Beginning of DIV

\includegraphics{figures/coordination-1}

% End of DIV

% Label
\label{pgfId-13187}
The approach taken to compute the inner product is to decompose the problem (of size
\emph{N}
) into smaller parts of size
\emph{K}
, where
\emph{N}
divides
\emph{K}
evenly. Then the same algorithm is used to work on the smaller parts. Of course, the result obtained by solving each part is only a partial result, so the partial results must be collected at the end to obtain the total result.
\par

% Label
\label{pgfId-13188}
In pseudocode,
\par

% Label
\label{pgfId-13192}
Let P = N / K, where P is the number of parts to work on.
\par

% Label
\label{pgfId-13193}
for j in 0..P-1 (this can be done concurrently)
\par

% Label
\label{pgfId-13198}
partialSum[j] = sum(vI * wI), for I in 0..K-1
\par

% Label
\label{pgfId-13201}
partialSum[j] = 0, for all j in 0..P-1
\par

% Label
\label{pgfId-13202}
totalSum = 0;
\par

% Label
\label{pgfId-13199}
for j in 0..P-1 (this must be done sequentially)
\par

% Label
\label{pgfId-13200}
totalSum += partialSum[j];
\par

% Label
\label{pgfId-13203}
The ability to do identical tasks concurrently is something we refer to as a
\emph{job jar}
. A job jar, much like a cookie jar, allows you to choose any task from the job jar and work on it. Here, the job jar will contain a pair of subvectors for which the (partial) inner product is to be computed.
\par

% Label
\label{pgfId-13344}
The code presented next shows the general structure of the
\texttt{VMpy}
class, which only consists of static methods that actually coordinate the basic computation. We will then walk through the various methods and explain what is going on. In order for this program to work, it must be run
\emph{P}
times, where
\emph{P}
corresponds to the number of parts into which the vector inner product has been decomposed.
\par

% Label
\label{pgfId-13380}

\par

	\begin{verbatim}
	

public class VMpy {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public static void main(String[] args)
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public static void createWork(MemoClient memo, int dim, int N)
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public static void doWork(MemoClient memo, int partNumber) 
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public static double mergeResults(MemoClient memo,int totalParts)
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public static class VectorPair implements Serializable { ... }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-13286}
The
\texttt{VMpy}
class is where you will find the pseudocode just shown. In fact, the pseudocode is found in the
\texttt{main()}
method. We’ll get to it shortly, but first we provide an explanation for the various static methods and other goodies found in this class:
\par

\begin{enumerate}

\item{main() : This is the actual driver for the entire computation. The command line is parsed here for the problem parameters and depending on the part being worked on, the remaining functions are called: createWork() , doWork() , and mergeResults() .}

\item{createWork() : This function is only called by the process that is working on part 0. It is used to define entries in the Memo space.}

\item{doWork() : This function is called by all processes. This function will get entries from the Memo space and put partial results back into the Memo space.}

\item{mergeResults() : This function is only called by the process that is working on part 0. This function basically collects all of the partial results from the Memo space and prints the final result.}

\end{enumerate}

% Label
\label{pgfId-13416}
The nested
\texttt{VectorPair}
class is used as a “wrapper” to package the work to be done. It simply holds references to two arrays of
\texttt{double}
(
\texttt{double[]}
) for which the partial inner product is to be computed. We chose to bundle the two arrays together in a single object to make it clear that the inner product is a job to be done that is placed in the job jar. When a given process gets the job from the job jar, it can simply tell the object to perform its task with little or no concern about how to actually do the task. In the case of the task, the
\texttt{innerProduct()}
method is called, which returns a
\texttt{Double}
value. This value can then be inserted into the
\texttt{Memo}
space as a (partial) result for later accumulation.
\par

	\begin{verbatim}
	

public static class VectorPair implements Serializable {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        int partNumber;
	\end{verbatim}
	
	\begin{verbatim}
	

        int dimension;
	\end{verbatim}
	
	\begin{verbatim}
	

        private double[] v;
	\end{verbatim}
	
	\begin{verbatim}
	

        private double[] w;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        public VectorPair(int partNumber, int dimension)
	\end{verbatim}
	
	\begin{verbatim}
	

        public Double innerProduct()
	\end{verbatim}
	
	\begin{verbatim}
	

   }
	\end{verbatim}
	
% Label
\label{pgfId-13407}
Let’s now discuss the code from the top down, starting from the
\texttt{main()}
method. This is shown as follows:
\par

	\begin{verbatim}
	

    public static void main(String[] args) {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            if (args.length < 5) {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.err.println(“VMpy host port dim part# N”);
	\end{verbatim}
	
	\begin{verbatim}
	

                return;
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

            String memoHost = args[0];
	\end{verbatim}
	
	\begin{verbatim}
	

            int memoPort = Integer.parseInt(args[1]);
	\end{verbatim}
	
	\begin{verbatim}
	

            int dimension = Integer.parseInt(args[2]);
	\end{verbatim}
	
	\begin{verbatim}
	

            int partNumber = Integer.parseInt(args[3]);
	\end{verbatim}
	
	\begin{verbatim}
	

            int totalParts = Integer.parseInt(args[4]);
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            if (dimension % totalParts != 0) {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.out.println(“dimension % totalParts != 0”);
	\end{verbatim}
	
	\begin{verbatim}
	

                return;
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            MemoClient mc = 
	\end{verbatim}
	
	\begin{verbatim}
	

              new MemoClient(memoHost, memoPort, “memo”);
	\end{verbatim}
	
	\begin{verbatim}
	

            if (partNumber == 0) {
	\end{verbatim}
	
	\begin{verbatim}
	

                createWork(mc, dimension, totalParts);
	\end{verbatim}
	
	\begin{verbatim}
	

                doWork(mc, partNumber);
	\end{verbatim}
	
	\begin{verbatim}
	

                double result = mergeResults(mc, totalParts);
	\end{verbatim}
	
	\begin{verbatim}
	

            } else 
	\end{verbatim}
	
	\begin{verbatim}
	

                doWork(mc,partNumber);
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch (Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            return;
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-13432}
The
\texttt{main()}
method is called by every worker that will participate in the calculation of the vector inner product. A number of parameters must be passed on the command line to determine what this particular worker will do:
\par

\begin{itemize}

\item{memoHost : This is the hostname to use to contact a MemoServer .}

% Label
\label{pgfId-13424}

\item{memoPort : This is the port number where the MemoServer is listening.}

% Label
\label{pgfId-13427}

\item{dimension : This stores the dimension of each vector. This code does not ensure that both vectors in fact have the same dimension.}

% Label
\label{pgfId-13428}

\item{partNumber : This holds the number the process will be responsible for working on.}

% Label
\label{pgfId-13435}

\item{totalParts : This is the total number of processes that will be participating in the computation.}

% Label
\label{pgfId-13436}

\end{itemize}

% Label
\label{pgfId-13437}
Once the command line parameters have been processed, the real work begins. The work to be performed depends on whether
\texttt{partNumber}
is zero. In parallel-computing applications, one of the parts usually has the added responsibility of creating the work to be done. By convention, this is usually part 0. The Memo system does not impose this requirement, unlike other message passing frameworks. Instead,
\texttt{Memo}
views process numbering as something beyond the scope of the framework that can be addressed by a process management framework.
\ref{#id(pgfId-13440)}[MISSING HREF]

\par

% Label
\label{pgfId-13438}
If the part number is zero (i.e., the “master”), the following methods are called:
\par

\begin{itemize}

\item{createWork() : This is used to decompose the work of the inner product into P parts and store them in the Memo space.}

% Label
\label{pgfId-13442}

\item{doWork() : Although the master is responsible for creating the work to be done, the master also participates in doing the work.}

% Label
\label{pgfId-13443}

\item{mergeResults() : The master will wait for all of the results to be computed by the various workers and put the final result together simply by adding up the partial sums.}

% Label
\label{pgfId-13444}

\end{itemize}

% Label
\label{pgfId-13445}
If the part number is nonzero, the
\texttt{doWork()}
method is the only method that is called.
\par

% Label
\label{pgfId-13449}
The
\texttt{createWork()}
method is as follows:
\par

	\begin{verbatim}
	

    public static void createWork(MemoClient memo, int dim, int N) {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            int blockSize = dim / N;
	\end{verbatim}
	
	\begin{verbatim}
	

            for (int i=0; i < N; i++) {
	\end{verbatim}
	
	\begin{verbatim}
	

                VectorPair vp = new VectorPair(i, blockSize);
	\end{verbatim}
	
	\begin{verbatim}
	

                memo.put(“pair” + i, vp);
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-13462}
The
\texttt{createWork()}
method is given a reference to the
\texttt{MemoClient}
object, the dimension of the vector(s), and the number of parts (
\emph{N}
).
\emph{N}

\texttt{VectorPair}
instances are created (randomly generated) and inserted into the
\texttt{MemoSpace}
. In the interests of safety, each of the entries in the
\texttt{Memo}
space is named “pair” +
\emph{i}
(i.e., “pair0”, “pair1”, ... “pair
\emph{N}
-1”) to ensure that every worker gets precisely one unit of work to do. It is not required to do this. You could simply put all of the work into key
\texttt{pair}
, and the
\texttt{SharedTableOfQueues}
will be smart enough to ensure that all of the entries are stored safely in the queue named
\texttt{pair}
.
\ref{#id(pgfId-13465)}[MISSING HREF]

\par

% Label
\label{pgfId-13466}
The
\texttt{doWork()}
method is responsible for doing the actual work (the actual work being the inner product itself). The code is as follows:
\par

	\begin{verbatim}
	

    public static void doWork(MemoClient memo, int partNumber) {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            VectorPair pair;
	\end{verbatim}
	
	\begin{verbatim}
	

            pair = (VectorPair) memo.get(“pair” + partNumber);
	\end{verbatim}
	
	\begin{verbatim}
	

            Double partialResult = pair.innerProduct();
	\end{verbatim}
	
	\begin{verbatim}
	

            memo.put(“partial” + partNumber, partialResult);
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-11464}
A
\texttt{VectorPair}
instance is retrieved from the
\texttt{Memo}
space. The worker uses its
\texttt{partNumber}
to determine which entry is to be retrieved. Now, the miracle of modern science occurs. The object is simply told to compute its inner product, and the result is stored in the
\texttt{Memo}
space under the name “partial” + partNumber. Thus, the inner product for the
\texttt{VectorPair}
contained in
\texttt{pair0}
will be stored in
\texttt{partial0}
,
\texttt{pair1}
in
\texttt{partial1}
, and so on. The
\texttt{mergeResults()}
code shows how the final result ultimtely is computed:
\par

	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

    public static double mergeResults(MemoClient memo, int totalParts) {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            double result = 0.0;
	\end{verbatim}
	
	\begin{verbatim}
	

            for (int i=0; i < totalParts; i++) {
	\end{verbatim}
	
	\begin{verbatim}
	

                Double partialResult;
	\end{verbatim}
	
	\begin{verbatim}
	

                partialResult = (Double) memo.get(“partial” + i);
	\end{verbatim}
	
	\begin{verbatim}
	

                result += partialResult.doubleValue();
	\end{verbatim}
	
	\begin{verbatim}
	

            } 
	\end{verbatim}
	
	\begin{verbatim}
	

            return result;
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            return 0.0;
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-11480}
Merging results together is actually very straightforward. A loop is established to
\texttt{get()}
the entries out of the
\texttt{Memo}
space. Recalling the original
\texttt{SharedTableOfQueues}
implementation, we see that the
\texttt{get()}
operation will block until the value actually becomes available--only this time the operation is working in a networked context. Although this step is sequential, everything leading up to this step was concurrent (and, in fact, parallel, if run on the network or a multiprocessor system). The result is returned and can be printed in the worker numbered zero.
\par

% Label
\label{pgfId-13480}
The
\texttt{VectorPair}
class is used to create the basic unit of work. This code is shown next. The
\texttt{VectorPair}
object itself must be
\texttt{Serializable}
, since it will be transmitted over the network using object serialization. The
\texttt{VectorPair}
object contains a package of work, which is two arrays--
\emph{v}
and
\emph{w}
--both with a common dimension and corresponding to a part number. Strictly speaking, the part number instance variable (
\texttt{partNumber}
) appears here only for the purpose of debugging via the
\texttt{toString()}
method.
\par

% Label
\label{pgfId-11500}
The nested
\texttt{VectorPair}
class is as follows:
\par

	\begin{verbatim}
	

  public static class VectorPair implements Serializable {
	\end{verbatim}
	
	\begin{verbatim}
	

        int partNumber;
	\end{verbatim}
	
	\begin{verbatim}
	

        int dimension;
	\end{verbatim}
	
	\begin{verbatim}
	

        private double[] v;
	\end{verbatim}
	
	\begin{verbatim}
	

        private double[] w;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        public VectorPair(int partNumber, int dimension) {
	\end{verbatim}
	
	\begin{verbatim}
	

            this.partNumber = partNumber;
	\end{verbatim}
	
	\begin{verbatim}
	

            this.dimension = dimension;
	\end{verbatim}
	
	\begin{verbatim}
	

            v = new double[dimension];
	\end{verbatim}
	
	\begin{verbatim}
	

            w = new double[dimension];
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            for (int i=0; i < dimension; i++) {
	\end{verbatim}
	
	\begin{verbatim}
	

                v[i] = Math.random() * 10.0;
	\end{verbatim}
	
	\begin{verbatim}
	

                w[i] = Math.random() * 10.0;
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        public Double innerProduct() {
	\end{verbatim}
	
	\begin{verbatim}
	

            double result = 0.0;
	\end{verbatim}
	
	\begin{verbatim}
	

            for (int i=0; i < dimension; i++)
	\end{verbatim}
	
	\begin{verbatim}
	

                result += v[i] * w[i];
	\end{verbatim}
	
	\begin{verbatim}
	

            return new Double(result);
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        public String toString() {
	\end{verbatim}
	
	\begin{verbatim}
	

            int i;
	\end{verbatim}
	
	\begin{verbatim}
	

            String result;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            result = “VectorPair: “ + partNumber + “ v: “;
	\end{verbatim}
	
	\begin{verbatim}
	

            for (i=0; i < dimension; i++)
	\end{verbatim}
	
	\begin{verbatim}
	

                result += “ “ + v[i];
	\end{verbatim}
	
	\begin{verbatim}
	

            result = “ w: “;
	\end{verbatim}
	
	\begin{verbatim}
	

            for (i=0; i < dimension; i++) 
	\end{verbatim}
	
	\begin{verbatim}
	

                result += “ “ + w[i];
	\end{verbatim}
	
	\begin{verbatim}
	

            return result;
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-13490}
A few details are in order regarding the VectorPair class. The constructor uses the random-number generator from the the
\texttt{Math}
class (a standard language class) to generate random data for the subvectors
\emph{v}
and
\emph{w}
. The
\texttt{innerProduct()}
method is used to compute the actual vector inner product and returns a
\texttt{Double}
object. The reason that an object is returned instead of a scalar value is to address the requirement that a
\texttt{Serializable}
entity be
\texttt{put()}
in the
\texttt{Memo}
space as a result. Recall that
\texttt{innerProduct()}
is called on the pair that is retrieved from the
\texttt{Memo}
space with a
\texttt{get()}
in the
\texttt{doWork()}
static method; the result is
\texttt{put()}
back into the
\texttt{Memo}
space, and the result must be
\texttt{Serializable}
, which means that it must be an object that is
\texttt{Serializable.}
(All Java
\texttt{Number}
subclasses and arrays are
\texttt{Serializable.}
)
\par

% Label
\label{pgfId-13495}
The following box explains how you can test this code:
\par

	%\begin{tabular}
	
% Label
\label{pgfId-13506}
Running the
\textbf{\texttt{VMpy}}
VMpyCode
	\begin{verbatim}
	

Running a parallel code is somewhat of a pain. You need to take care to ensure that everything is started correctly.
	\end{verbatim}
	
	\begin{verbatim}
	

First, the 
Memo
 server must be started. We have implemented a 
MemoServer
 that can be used to serve a 
SharedTableOfQueues
 to any application that wants to use it.
	\end{verbatim}
	
	\begin{verbatim}
	

To start the 
MemoServer
 on port 2099 (you can start on ANY port desired), use
	\end{verbatim}
	
	\begin{verbatim}
	

java jhpc.memo.MemoServer$Server 2099
	\end{verbatim}
	
	\begin{verbatim}
	

Then, start 
N
 copies of the 
VMpy
 class. It does not matter how many copies you start, as long as you take care to ensure that each part is started correctly.
	\end{verbatim}
	
	\begin{verbatim}
	

Suppose you want to compute the inner product of two vectors with dimension 1000 using 5 processes. You’d do the following:
	\end{verbatim}
	
	\begin{verbatim}
	

java jhpc.memo.VMpy localhost 2099 1000 0 5
	\end{verbatim}
	
	\begin{verbatim}
	

java jhpc.memo.VMpy localhost 2099 1000 1 5
	\end{verbatim}
	
	\begin{verbatim}
	

java jhpc.memo.VMpy localhost 2099 1000 2 5
	\end{verbatim}
	
	\begin{verbatim}
	

java jhpc.memo.VMpy localhost 2099 1000 3 5
	\end{verbatim}
	
	\begin{verbatim}
	

java jhpc.memo.VMpy localhost 2099 1000 4 5
	\end{verbatim}
	
	\begin{verbatim}
	

On the CD, we provide two scripts: 
run-me-local
 and 
run-me-remote
. You can use these scripts to automate these tasks on Unix or Windows. (Windows scripts have a 
.bat
 extension.) The 
run-me-local
 script simply runs everything on a single host. (
localhost
 may need to be replaced by 
127.0.0.1
, the loopback address, in your environment.) The 
run-me-remote
 script can be used on Unix with 
rsh
 or 
ssh 
capability to start the various processes on different hosts.
	\end{verbatim}
	
	%\end{tabular}
	
\section{Trapezoidal Integration}

% Label
\label{pgfId-11332}

% Label
\label{39646}

% Label
\label{pgfId-13537}
Earlier in the book, we presented trapezoidal integration. In trapezoidal integration, the goal is to find the area under the curve by subdividing the interval and approximating each subdivision as a trapezoid. The earlier version of this code essentially created a thread to compute the total area in a region. (The class
\texttt{IntegTrapRegion}
was used for this purpose and is reused here.)
\par

% Label
\label{pgfId-13541}
Despite being a different problem than the vector inner product that was discussed in the previous section, there are striking similarities between how this problem and the vector inner product problem are attacked with the
\texttt{Memo}
system. As before, there is one part that is responsible for creating the work, doing the work, and merging the partial results together, while the other parts simply do their share of the work and write their partial results to the
\texttt{Memo}
space.
\par

% Label
\label{pgfId-13542}
The complete code is available on the book CD and Web site in the class
\texttt{IntegTrapMemo}
. We now provide an overview of the key methods: the
\texttt{main()}
method (the driver) and the various methods that play a role in defining and doing the work.
\par

% Label
\label{pgfId-13546}
The
\texttt{main()}
method is as follows.
\par

	\begin{verbatim}
	

    public static void main(String args[]) {
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            String usage;
	\end{verbatim}
	
	\begin{verbatim}
	

            usage = “ITM host port part# parts start end gran”
	\end{verbatim}
	
	\begin{verbatim}
	

            if (args.length < 7)  {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.err.println(“usage: “ + usage);
	\end{verbatim}
	
	\begin{verbatim}
	

                return;
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

            String memoHost = args[0];
	\end{verbatim}
	
	\begin{verbatim}
	

            int memoPort = Integer.parseInt(args[1]);
	\end{verbatim}
	
	\begin{verbatim}
	

            int partNumber = Integer.parseInt(args[2]);
	\end{verbatim}
	
	\begin{verbatim}
	

            int numParts = Integer.parseInt(args[3]);
	\end{verbatim}
	
	\begin{verbatim}
	

            double start = new Double(args[4]).doubleValue();
	\end{verbatim}
	
	\begin{verbatim}
	

            double end = new Double(args[5]).doubleValue();
	\end{verbatim}
	
	\begin{verbatim}
	

            int gran = Integer.parseInt(args[6]);
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            MemoClient mc;
	\end{verbatim}
	
	\begin{verbatim}
	

            mc = new MemoClient(memoHost, memoPort, “memo”);
	\end{verbatim}
	
	\begin{verbatim}
	

            if (partNumber == 0) {
	\end{verbatim}
	
	\begin{verbatim}
	

                createWork(mc, numParts, start, end, gran);
	\end{verbatim}
	
	\begin{verbatim}
	

                doWork(mc, partNumber);
	\end{verbatim}
	
	\begin{verbatim}
	

                double result = mergeResults(mc, numParts);
	\end{verbatim}
	
	\begin{verbatim}
	

                mc.disconnect();
	\end{verbatim}
	
	\begin{verbatim}
	

            } else {
	\end{verbatim}
	
	\begin{verbatim}
	

                doWork(mc,partNumber);
	\end{verbatim}
	
	\begin{verbatim}
	

                mc.disconnect();
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        } catch (Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

            e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            return;
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-11610}
As done in the vector inner product, (
\texttt{VMpy}
), the parameters are obtained from the command line. These parameters are now explained:
\par

	\begin{verbatim}
	

String memoHost = args[0];
	\end{verbatim}
	
\begin{itemize}

\item{memoHost (args[0]) : This stores the host where the Memo server has been started.}

% Label
\label{pgfId-13551}

\item{memoPort (args[1]) : This is the port on which the Memo server is listening.}

% Label
\label{pgfId-13559}

\item{partNumber (args[2]) : This worker is part “partNumber” of “numParts”}

% Label
\label{pgfId-13552}

\item{numParts (args[3]) : This holds the total number of workers.}

% Label
\label{pgfId-13553}

\item{start (args[4]) : This is the x -value to start integration.}

% Label
\label{pgfId-13554}

\item{end (args[5]) : This is the x -value to end integration.}

% Label
\label{pgfId-13555}

\item{gran (args[6]) : This is the granularity (number of trapezoids per worker)}

% Label
\label{pgfId-13556}

\end{itemize}

% Label
\label{pgfId-13562}
Once the parameters have been obtained, a connection is made to the
\texttt{Memo}
server as before. Then, based on the value obtained for partNumber, a determination is made whether or not the
\texttt{partNumber}
is zero. If it is, the worker has the added responsibility of defining the work to be done and then proceeds to do the work, followed by a merge of the results. Otherwise, the worker simply does its share of the overall trapezoidal integration. These functions are virtually identical to the work done in vector inner product with the notable differences being the parameters from the command line and the actual computation performed. We’ll get to this in a minute.
\par

% Label
\label{pgfId-13565}
The
\texttt{createWork()}
function appears as follows:
\par

	\begin{verbatim}
	

    public static void createWork(MemoClient mc, int num_t,
	\end{verbatim}
	
	\begin{verbatim}
	

      double start, double end, int gran) {
	\end{verbatim}
	
	\begin{verbatim}
	

        function fn = new function();
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        partition( mc, num_t, start, end, gran, fn );
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-11626}
This function simply calls the
\texttt{partition()}
function, which was excised from the original program, after creating a
\texttt{function}
instance. Recalling the earlier discussion, we find that Java does not have function parameter passing as found in other programming languages (C and C++). The idiom is emulated in Java by creating an interface (
\texttt{F\underscore{}of\underscore{}x}
) and then creating a class that implements the interface (
\texttt{function}
):
\par

	\begin{verbatim}
	

    public static void partition( 
MemoClient space
, 
	\end{verbatim}
	
	\begin{verbatim}
	

       int numThreads, double a, double b, int granularity,
	\end{verbatim}
	
	\begin{verbatim}
	

       F_of_x fn )
	\end{verbatim}
	
	\begin{verbatim}
	

    {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        try { 
	\end{verbatim}
	
	\begin{verbatim}
	

            if( numThreads < 1 )
	\end{verbatim}
	
	\begin{verbatim}
	

                throw new BadThreadCountException();
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            if( a > b )
	\end{verbatim}
	
	\begin{verbatim}
	

                throw new BadRangeException();
	\end{verbatim}
	
	\begin{verbatim}
	

            
	\end{verbatim}
	
	\begin{verbatim}
	

            if( a == b )
	\end{verbatim}
	
	\begin{verbatim}
	

                throw new NoRangeException();
	\end{verbatim}
	
	\begin{verbatim}
	

            
	\end{verbatim}
	
	\begin{verbatim}
	

            if( granularity < 1 )
	\end{verbatim}
	
	\begin{verbatim}
	

                throw new BadGranularityException();
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

        catch( Exception e ) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println( e.toString() );
	\end{verbatim}
	
	\begin{verbatim}
	

            System.exit( 1 );
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        long begin_time = 0;
	\end{verbatim}
	
	\begin{verbatim}
	

        long end_time = 0;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            double range = b - a;
	\end{verbatim}
	
	\begin{verbatim}
	

            double start = a;
	\end{verbatim}
	
	\begin{verbatim}
	

            double end = a + ((1.0d)/numThreads * range);
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            begin_time = System.currentTimeMillis();
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            for( int i=0; i < numThreads; i++ ) {
	\end{verbatim}
	
	\begin{verbatim}
	

               
 space.put(“region”+i, 

	\end{verbatim}
	
	\begin{verbatim}
	


                   new IntegTrapRegion(start,end,granularity,fn));

	\end{verbatim}
	
	\begin{verbatim}
	

                start = end;
	\end{verbatim}
	
	\begin{verbatim}
	

                end = a + ((i + 2.0d)/numThreads * range);
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

        catch( Exception e ) {
	\end{verbatim}
	
	\begin{verbatim}
	

            System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-13568}
The code for the
\texttt{partition()}
function appeared in the original
\texttt{IntegTrap}
code. The notable difference appears in boldface. Where the original code would have created an
\texttt{IntegTrapRegion}
instance and then called the
\texttt{Thread start()}
method, this code simply uses the
\texttt{Memo put()}
function to create an entry in the
\texttt{Memo}
system. This entry is retrieved by one of the workers that calls the
\texttt{doWork()}
method, which appears as follows:
\par

	\begin{verbatim}
	

    public static void doWork(MemoClient space, int partNumber)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception{
	\end{verbatim}
	
	\begin{verbatim}
	

        IntegTrapRegion region;
	\end{verbatim}
	
	\begin{verbatim}
	

        region = (IntegTrapRegion)space.get(“region”+partNumber);
	\end{verbatim}
	
	\begin{verbatim}
	

        region.run();
	\end{verbatim}
	
	\begin{verbatim}
	

        space.put(“partial”+partNumber, region);
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-13571}
As done in the vector-inner-product example, every participant worker will get its work from the
\texttt{Memo}
space. This work will be an instance of
\texttt{IntegTrapRegion}
(which was
\texttt{put()}
in the
\texttt{createWork()}
method). Here, we do the work simply by calling the
\texttt{run()}
method explicitly. This was mostly done out of laziness; however, it also shows that with few code changes, we can modify a code that was never designed to work in a networked fashion to work with the
\texttt{Memo}
system.
\par

% Label
\label{pgfId-13581}
Finally, we perform the now-familiar task of merging the results. Again, we rely on the
\texttt{get()}
method to block for each partial result and (once unblocked) simply accumulate the sum of partial values. The code is as follows:
\par

	\begin{verbatim}
	

    public static double mergeResults(MemoClient space, int num_t)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	

        double totalArea = 0.0;
	\end{verbatim}
	
	\begin{verbatim}
	

        for (int i=0; i < num_t; i++)  {
	\end{verbatim}
	
	\begin{verbatim}
	

            IntegTrapRegion thisArea;
	\end{verbatim}
	
	\begin{verbatim}
	

            thisArea = (IntegTrapRegion) space.get(“partial”+i);
	\end{verbatim}
	
	\begin{verbatim}
	

            totalArea += partialArea.getArea();
	\end{verbatim}
	
	\begin{verbatim}
	

        } 
	\end{verbatim}
	
	\begin{verbatim}
	

        return totalArea; 
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-13582}
The
\texttt{IntegTrapMemo}
example shows that we can work almost exclusively with objects. In the vector-inner-product example, we computed a
\texttt{Double}
object value from the result of the inner product computed for a given
\texttt{VectorPair}
instance. This was, strictly speaking, not necessary. We could have simply computed the result as part of the object’s state and then
\texttt{put()}
it under a different name in the
\texttt{Memo}
space.
\ref{#id(pgfId-13584)}[MISSING HREF]

\par

% Label
\label{pgfId-13590}
Running the
\texttt{IntegTrapMemo}
code is almost identical to running the
\texttt{VMpy}
code. Scripts are provided to ameliorate the task of starting up the various processes on your favorite operating system (Linux, other Unix environment, or Windows).
\par

\section{Warshall’s Algorithm}

% Label
\label{pgfId-11333}

% Label
\label{21991}

% Label
\label{pgfId-13591}
The third and final example we consider is Warshall’s algorithm. Warshall’s algorithm was also presented earlier in the book, and it represents one of the more difficult algorithms to make work in parallel. Here, we show how to extend the parallel version to use the
\texttt{Memo}
system.
\par

% Label
\label{pgfId-13592}
The entire code for this example can be found on the book CD and Web site in class
\texttt{WarshallTQ}
. In the interests of conciseness, we highlight the design and leave the “rest of the story” to self-study and a future book.
\par

% Label
\label{pgfId-13597}
To get this code to work with
\texttt{Memo}
, a bit of minor restructuring needed to be done. The first and foremost consideration is the assumptions made by the earlier code about shared memory. In particular, the boolean matrix
\texttt{a}
was assumed to be shared among all of the threads. In fact, only one thread (the master thread, part 0 again) really needs to know about this boolean matrix. All of the threads are computing a part of the closure, which is stored in the
\texttt{Block}
class. To ensure that no sharing occurred, we eliminated
\texttt{Block}
as an inner class in the original design; it now appears as a separate class.
\ref{#id(pgfId-13599)}[MISSING HREF]

\par

% Label
\label{pgfId-13602}
At the top level, the code appears to have much in common with the two previous examples. Part 0 basically creates work, does work, and merges results; the other parts simply do work. The key difference between this example and the previous ones is that this algorithm computes a very large result (the closure boolean matrix). The boolean matrix is decomposed into blocks, the closure is performed in parallel, and then a resultant matrix is obtained. Thus, we are not simply computing a scalar value as in the two previous examples, but rather a matrix.
\par

% Label
\label{pgfId-13601}
Let us now consider the relevant methods of the
\texttt{WarshallTQ}
class, which will be followed by a discussion of the
\texttt{Block}
class, wherein the actual closure is computed.
\par

% Label
\label{pgfId-13656}
The following is the
\texttt{main()}
method:
\par

	\begin{verbatim}
	

       public static void main(String args[]) {
	\end{verbatim}
	
	\begin{verbatim}
	

            String usage;
	\end{verbatim}
	
	\begin{verbatim}
	

            usage = “ITM host port part# parts start end gran”;
	\end{verbatim}
	
	\begin{verbatim}
	

            if (args.length < 6)  {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.err.println(“usage: ” + usage);
	\end{verbatim}
	
	\begin{verbatim}
	

                return;
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            try { 
	\end{verbatim}
	
	\begin{verbatim}
	

                int i,j;
	\end{verbatim}
	
	\begin{verbatim}
	

                double probTrue = 0.3;
	\end{verbatim}
	
	\begin{verbatim}
	

                String memoHost = args[0];
	\end{verbatim}
	
	\begin{verbatim}
	

                int memoPort = Integer.parseInt(args[1]);
	\end{verbatim}
	
	\begin{verbatim}
	

                int partNumber = Integer.parseInt(args[2]);
	\end{verbatim}
	
	\begin{verbatim}
	

                int numParts = Integer.parseInt(args[3]);
	\end{verbatim}
	
	\begin{verbatim}
	

                int N = Integer.parseInt(args[4]);
	\end{verbatim}
	
	\begin{verbatim}
	

                int bsize = Integer.parseInt(args[5]);
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

                boolean a[][]=new boolean[N][N];        
	\end{verbatim}
	
	\begin{verbatim}
	

                Random rand = new Random();
	\end{verbatim}
	
	\begin{verbatim}
	

                for(i=0; i< N; i++ ) {
	\end{verbatim}
	
	\begin{verbatim}
	

                    for(j=0; j<N; j++ ) {
	\end{verbatim}
	
	\begin{verbatim}
	

                        a[i][j] = (rand.nextDouble() <= probTrue);
	\end{verbatim}
	
	\begin{verbatim}
	

                    }
	\end{verbatim}
	
	\begin{verbatim}
	

                }
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            
	\end{verbatim}
	
	\begin{verbatim}
	

                WarshallTQ w;
	\end{verbatim}
	
	\begin{verbatim}
	

                w= new WarshallTQ(memoHost,memoPort,”memo”,bsize);
	\end{verbatim}
	
	\begin{verbatim}
	

                if (partNumber == 0) {
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.connectToMemo();
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.closureCreateWork(a);
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.closureDoWork(partNumber,numParts);
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.closureMergeResults(a);
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.disconnect();
	\end{verbatim}
	
	\begin{verbatim}
	

                } else {
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.connectToMemo();
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.closureDoWork(partNumber, numParts);
	\end{verbatim}
	
	\begin{verbatim}
	

                    w.disconnect();
	\end{verbatim}
	
	\begin{verbatim}
	

                }
	\end{verbatim}
	
	\begin{verbatim}
	

            } catch(Exception e) {
	\end{verbatim}
	
	\begin{verbatim}
	

                System.out.println(e);
	\end{verbatim}
	
	\begin{verbatim}
	

                e.printStackTrace();
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
% Label
\label{pgfId-13603}
As before, more than half of the code in this method is dedicated to obtaining parameters. The parameters include the following:
\par

\begin{itemize}

\item{memoHost : This is where the Memo server is running.}

% Label
\label{pgfId-13658}

\item{memoPort : This stores the port where the Memo server is listening.}

% Label
\label{pgfId-13659}

\item{numParts : This holds the total number of workers.}

% Label
\label{pgfId-13660}

\item{N : This is the dimension of the matrix.}

% Label
\label{pgfId-13661}

\item{bsize : This is the block size.}

% Label
\label{pgfId-13662}

\end{itemize}

% Label
\label{pgfId-13667}
After the parameters are obtained, a boolean matrix is generated randomly. If you wanted to provide your own boolean matrix from an input file, you could replace the code that appears here. Then, a
\texttt{WarshallTQ}
object is created. Connections to
\texttt{Memo}
are actually managed by the
\texttt{WarshallTQ}
object via the
\texttt{connectToMemo()}
method, which uses the
\texttt{memoHost}
,
\texttt{memoPort}
, and
\texttt{memo}

\texttt{Memo}
space name to make connections on demand.
\par

% Label
\label{pgfId-13686}
The code in the
\texttt{main()}
method for the master (part 0) is very similar to the previous two examples:
\par

\begin{enumerate}

\item{A connection is made to the Memo system:}

\end{enumerate}

	\begin{verbatim}
	

		w.connectToMemo();
	\end{verbatim}
	
\begin{enumerate}

\item{The work is created, and a reference to the boolean matrix ( a ) is passed:}

\end{enumerate}

	\begin{verbatim}
	

		w.closureCreateWork(a);
	\end{verbatim}
	
\begin{enumerate}

\item{As in the two previous examples, the work is done. partNumber and numParts are needed to determine what blocks a worker will work on (it is not necessarily the case in this algorithm that the number of workers evenly divides the number of blocks, so this is done to keep the code general!):}

\end{enumerate}

	\begin{verbatim}
	

		w.closureDoWork(partNumber,numParts);
	\end{verbatim}
	
\begin{enumerate}

\item{The master is responsible for ensuring that all of the blocks have been computed. It will do this in the closureMergeResults() method and replace the original boolean matrix ( a ) with its closure one block at a time:}

\end{enumerate}

	\begin{verbatim}
	

		w.closureMergeResults(a);
	\end{verbatim}
	
\begin{enumerate}

\item{This is done to politely inform the Memo system that the work is done.}

\end{enumerate}

	\begin{verbatim}
	

		w.disconnect();
	\end{verbatim}
	
% Label
\label{pgfId-13687}
The code in the
\texttt{main()}
method for the other parts simply performs steps 1, 3, and 5. Steps 2 and 4 are only done by part 0.
\par

% Label
\label{pgfId-13706}
Let us now consider the details of some of these methods. The
\texttt{closureCreateWork()}
method is presented next and is a method of the
\texttt{WarshallTQ}
class:
\par

	\begin{verbatim}
	

    public void closureCreateWork(boolean[][] a) throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	

        int i,j,NR,NC;
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        IndexedKey kthRows=IndexedKey.unique(0);
	\end{verbatim}
	
	\begin{verbatim}
	

        IndexedKey kthCols=IndexedKey.unique(0);
	\end{verbatim}
	
	\begin{verbatim}
	

        NR=a.length;
	\end{verbatim}
	
	\begin{verbatim}
	

        NC=a[0].length;
	\end{verbatim}
	
	\begin{verbatim}
	

        int nt=((NR+blkSize-1)/blkSize)*((NC+blkSize-1)/blkSize);
	\end{verbatim}
	
	\begin{verbatim}
	

        for (i=0;i<NR;i+=blkSize) 
	\end{verbatim}
	
	\begin{verbatim}
	

            for (j=0;j<NC;j+=blkSize){
	\end{verbatim}
	
	\begin{verbatim}
	

                Block b;
	\end{verbatim}
	
	\begin{verbatim}
	

                b = new Block(a,i,j,kthRows,kthCols,blkSize);
	\end{verbatim}
	
	\begin{verbatim}
	

                
space.put(“block”, b);

	\end{verbatim}
	
	\begin{verbatim}
	

                numBlocks++;
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	

        
space.put(“blockCount”, new Integer(numBlocks));

	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-11816}
In the earlier version of the Warshall code, the lines that appear in boldface did not exist. The first of these two lines contained a call to the
\texttt{Thread start()}
method to actually start the computation on the block immediately. (The earlier version of
\texttt{WarshallTQ}
did actually make use of the
\texttt{SharedTableOfQueues}
, but only when evaluating the block itself. We use the
\texttt{Memo}
system to actually store the block, so multiple workers can contend for the different blocks and perform work.)
\par

% Label
\label{pgfId-13707}
The second of these two boldfaced lines write a single entry,
\texttt{blockCount}
, that will be used by all parts of the computation to determine how many total blocks there are to be worked on. This global block count will allow us to demonstrate the power of
\texttt{Memo}
to address the need for global values, which can be obtained via the
\texttt{getCopy()}
method from the
\texttt{SharedTableOfQueues}
abstraction.
\par

% Label
\label{pgfId-13708}
Once we have the work defined, we can think about actually doing the work. The
\texttt{closureDoWork()}
method does just that:
\par

	\begin{verbatim}
	

    public void closureDoWork(int workerNumber,
	\end{verbatim}
	
	\begin{verbatim}
	

                              int numberOfWorkers)
	\end{verbatim}
	
	\begin{verbatim}
	

        throws Exception{
	\end{verbatim}
	
	\begin{verbatim}
	

        int numBlocksToWorkOn, remainder;
	\end{verbatim}
	
	\begin{verbatim}
	

        Integer globalBlockCount;
	\end{verbatim}
	
	\begin{verbatim}
	

        globalBlockCount = (Integer)space.getCopy(“blockCount”);
	\end{verbatim}
	
	\begin{verbatim}
	

        Vector blocks = new Vector();
	\end{verbatim}
	
	\begin{verbatim}
	

        Vector spaces = new Vector();
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

        int numBlocks = globalBlockCount.intValue();
	\end{verbatim}
	
	\begin{verbatim}
	

       
 for (int j=workerNumber; j < numBlocks;

	\end{verbatim}
	
	\begin{verbatim}
	


                 j += numberOfWorkers)

	\end{verbatim}
	
	\begin{verbatim}
	


        {

	\end{verbatim}
	
	\begin{verbatim}
	


            Block b = (Block) space.get(“block”);

	\end{verbatim}
	
	\begin{verbatim}
	


            MemoClient newSpace;

	\end{verbatim}
	
	\begin{verbatim}
	


            newSpace = new MemoClient(memoHost,memoPort,“memo”);

	\end{verbatim}
	
	\begin{verbatim}
	


            spaces.addElement(newSpace);

	\end{verbatim}
	
	\begin{verbatim}
	


            blocks.addElement(b);

	\end{verbatim}
	
	\begin{verbatim}
	


            b.setMemoClient(newSpace);

	\end{verbatim}
	
	\begin{verbatim}
	


            b.start();

	\end{verbatim}
	
	\begin{verbatim}
	


        }

	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	


        Enumeration bEnum = blocks.elements();

	\end{verbatim}
	
	\begin{verbatim}
	


        while (bEnum.hasMoreElements()) {

	\end{verbatim}
	
	\begin{verbatim}
	


           Block b = (Block) bEnum.nextElement();

	\end{verbatim}
	
	\begin{verbatim}
	


           try {

	\end{verbatim}
	
	\begin{verbatim}
	


             b.join();

	\end{verbatim}
	
	\begin{verbatim}
	


           } catch(Exception e) {}

	\end{verbatim}
	
	\begin{verbatim}
	


        }

	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	


        Enumeration sEnum = blocks.elements();

	\end{verbatim}
	
	\begin{verbatim}
	


        while (sEnum.hasMoreElements()) {

	\end{verbatim}
	
	\begin{verbatim}
	


           MemoClient s = (MemoClient) sEnum.nextElement();

	\end{verbatim}
	
	\begin{verbatim}
	


           try {

	\end{verbatim}
	
	\begin{verbatim}
	


             s.goodbye();

	\end{verbatim}
	
	\begin{verbatim}
	


           } catch(Exception e) {}

	\end{verbatim}
	
	\begin{verbatim}
	


        }

	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-11850}
This method required a few enhancements from the original code. Boldface has been used to indicate the changes that needed to be performed. A block is retrieved from the
\texttt{Memo}
space. Then, a new connection is made to the
\texttt{Memo}
space to give each
\texttt{Block}
its own communication channel to the Memo system.
\ref{#id(pgfId-13713)}[MISSING HREF]
Then, (as before) the
\texttt{Block}
instance is started as a thread. Each worker creates threads to execute a subset of the
\texttt{Block}
instances that are needed to compute the closure.
\par

% Label
\label{pgfId-13726}
Partitioning is a common technique that is used in parallel computing when multiple (numbered) workers are employed to do a set of numbered tasks. This is exemplified by the following loop that appears in
\texttt{closureDoWork()}
:
\par

	\begin{verbatim}
	

   for (int j=workerNumber; j < numBlocks; j += numberOfWorkers)
	\end{verbatim}
	
% Label
\label{pgfId-13716}
This is a particularly elegant way of dealing with the situation where the number of blocks does not evenly divide the number of workers. Consider what will happen when there are three workers (
\texttt{numberOfWorkers = 3}
) and 10 blocks (
\texttt{numBlocks = 10}
). The following values of
\texttt{j}
will be observed for workers 0, 1, and 2 (which represent all of the workers by number):
\par

	\begin{verbatim}
	

	worker			j values observed
	\end{verbatim}
	
	\begin{verbatim}
	

	0			0, 3, 6, 9
	\end{verbatim}
	
	\begin{verbatim}
	

	1			1, 4, 7
	\end{verbatim}
	
	\begin{verbatim}
	

	2			2, 5, 8
	\end{verbatim}
	
% Label
\label{pgfId-13715}
This is precisely what would be expected. Because the total number of blocks to be worked on is 10, each worker is going to work on a minimum of three blocks. One worker will work on four blocks.
\par

% Label
\label{pgfId-13736}
The rest of the code in this method is dedicated to joining all threads (to ensure that all of the
\texttt{Block}
instances have completed their part of the closure) and taking down the connections to the
\texttt{Memo}
space. The
\texttt{Vector}
instances that appear in this code (blocks and space) appear here for the purpose of keeping track of all of the blocks we’re working on, as well as the connections that have been made, thus making for very easy bookkeeping.
\par

% Label
\label{pgfId-13711}
Whew! The final step is to merge the results together in much the same fashion as done in the preceding examples. The code for
\texttt{closureMergeResults()}
is now shown:
\par

	\begin{verbatim}
	

    public void closureMergeResults(boolean[][] a)
	\end{verbatim}
	
	\begin{verbatim}
	

      throws Exception {
	\end{verbatim}
	
	\begin{verbatim}
	

        for (int i=0; i < numBlocks; i++) {
	\end{verbatim}
	
	\begin{verbatim}
	


	\end{verbatim}
	
	\begin{verbatim}
	

            Block result = (Block) space.get(“blockClosure”);
	\end{verbatim}
	
	\begin{verbatim}
	

            result.merge(a);
	\end{verbatim}
	
	\begin{verbatim}
	

        }
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-11863}
That’s it. It is just a matter of getting the
\texttt{blockClosure}
result that was written by the
\texttt{closureDoWork()}
method and then telling the object to replace its part of the boolean matrix (a) with its submatrix.
\par

% Label
\label{pgfId-13752}
In the foregoing discussion, we made unresolved “forward” references to two aspects of the
\texttt{Block}
class, which exists for the sole purpose of holding part of the boolean matrix (a submatrix) and performing the closure.
\par

% Label
\label{pgfId-13753}
The actual work of the closure is done in the
\texttt{run()}
method, which is shown next (the
\texttt{Block}
class is virtually unchanged from the original code, except that it now appears as a separate, unnested class):
\par

	\begin{verbatim}
	

    public void run(){
	\end{verbatim}
	
	\begin{verbatim}
	

        int i,j;
	\end{verbatim}
	
	\begin{verbatim}
	

        int k;
	\end{verbatim}
	
	\begin{verbatim}
	

        boolean IHaveRow,IHaveColumn;
	\end{verbatim}
	
	\begin{verbatim}
	

        boolean[] row=null, col=null;
	\end{verbatim}
	
	\begin{verbatim}
	

        try {
	\end{verbatim}
	
	\begin{verbatim}
	

            for (k=0;k<N;k++) {
	\end{verbatim}
	
	\begin{verbatim}
	

                IHaveRow = k-r>=0 && k-r < nr;              
	\end{verbatim}
	
	\begin{verbatim}
	

                IHaveColumn = k-c>=0 && k-c < nc;
	\end{verbatim}
	
	\begin{verbatim}
	

                if (IHaveRow) {
	\end{verbatim}
	
	\begin{verbatim}
	


                    BooleanArray myRow;

	\end{verbatim}
	
	\begin{verbatim}
	


                    myRow = new BooleanArray(block[k-r]);

	\end{verbatim}
	
	\begin{verbatim}
	


                    space.put(rows.at(k+c*N), myRow);

	\end{verbatim}
	
	\begin{verbatim}
	

                    row = block[k-r];
	\end{verbatim}
	
	\begin{verbatim}
	

                }           
	\end{verbatim}
	
	\begin{verbatim}
	

                if (IHaveColumn) {
	\end{verbatim}
	
	\begin{verbatim}
	


                    col=new boolean[nr];

	\end{verbatim}
	
	\begin{verbatim}
	


                    for (j=0;j<nr;j++) col[j]=block[j][k-c];

	\end{verbatim}
	
	\begin{verbatim}
	


                    BooleanArray myCol;

	\end{verbatim}
	
	\begin{verbatim}
	

                    myCol = new BooleanArray(col)
	\end{verbatim}
	
	\begin{verbatim}
	

                    space.put(cols.at(k+r*N), myCol);
	\end{verbatim}
	
	\begin{verbatim}
	

                }           
	\end{verbatim}
	
	\begin{verbatim}
	

                if (!IHaveRow) {
	\end{verbatim}
	
	\begin{verbatim}
	

 
                   BooleanArray r;

	\end{verbatim}
	
	\begin{verbatim}
	


                    r = (BooleanArray) space.get(rows.at(k+c*N));

	\end{verbatim}
	
	\begin{verbatim}
	


                    row = r.getData();

	\end{verbatim}
	
	\begin{verbatim}
	

                }           
	\end{verbatim}
	
	\begin{verbatim}
	

                if (!IHaveColumn) {
	\end{verbatim}
	
	\begin{verbatim}
	

                    BooleanArray c;
	\end{verbatim}
	
	\begin{verbatim}
	

                    
c = (BooleanArray) space.get(cols.at(k+r*N));

	\end{verbatim}
	
	\begin{verbatim}
	


                    col = c.getData();

	\end{verbatim}
	
	\begin{verbatim}
	

                }
	\end{verbatim}
	
	\begin{verbatim}
	

                for (i=0;i<nr;i++)
	\end{verbatim}
	
	\begin{verbatim}
	

                    if (col[i]) 
	\end{verbatim}
	
	\begin{verbatim}
	

                        for (j=0;j<nc;j++)
	\end{verbatim}
	
	\begin{verbatim}
	

                            block[i][j] |= row[j];
	\end{verbatim}
	
	\begin{verbatim}
	

            }
	\end{verbatim}
	
	\begin{verbatim}
	


            space.put(“blockClosure”, this);

	\end{verbatim}
	
	\begin{verbatim}
	

        }catch (InterruptedException iex){}
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
% Label
\label{pgfId-12159}
The differences between the original version of
\texttt{Block}
’s
\texttt{run()}
method and this version are what would be expected. We are now interacting with
\texttt{Memo}
. A
\texttt{BooleanArray}
wrapper class has been used (but is not shown here). This was not strictly necessary; however, it made debugging somewhat easier.
\ref{#id(pgfId-13758)}[MISSING HREF]
Basically, instead of writing the data to a local
\texttt{SharedTableOfQueues}
, the data are written to the
\texttt{Memo}
space reference. Each
\texttt{Block}
has its own connection to the
\texttt{Memo}
server, which you can verify by studying the full source code. The changes are shown in boldface. The very last boldface line of code shows that the
\texttt{Block}
instance is saved as a different entry in the
\texttt{Memo}
space, once its part of the closure is completed (hence the presence of
\texttt{this}
as the subject of the
\texttt{put()}
method call).
\par

% Label
\label{pgfId-13762}
The merge code was formerly a part of the
\texttt{Block run()}
method. It now appears separately, since the merging must be done where the boolean matrix
\texttt{a}
is located. It is provided as a method in
\texttt{Block}
, since a
\texttt{Block}
instance is the only place where the knowledge of where the data came from in the original boolean matrix. The following is the code for
\texttt{Merge()}
:
\par

	\begin{verbatim}
	

    public void merge(boolean[][] a) {
	\end{verbatim}
	
	\begin{verbatim}
	

        for (int i=0;i<nr;i++)
	\end{verbatim}
	
	\begin{verbatim}
	

            for (int j=0;j<nc;j++)
	\end{verbatim}
	
	\begin{verbatim}
	

                a[r+i][c+j]=block[i][j];
	\end{verbatim}
	
	\begin{verbatim}
	

    }
	\end{verbatim}
	
	\begin{verbatim}
	

}
	\end{verbatim}
	
% Label
\label{pgfId-12167}
And that’s all there is to it.
\par

\section{Chapter Wrap-up}

% Label
\label{pgfId-13763}

% Label
\label{10454}

% Label
\label{pgfId-13764}
It is impossibe to do complete justice to process coordination in a book that is largely dedicated to working with threads. The
\texttt{Memo}
system is really a very lightweight implementation of a tuple space that has more of a client-server flavor than a peer-to-peer one. We are actively engaged in other projects that are more peer oriented than client-server oriented. Nonetheless,
\texttt{Memo}
provides an excellent starting point for those who want to learn what is behind the various message passing systems that are out there.
\texttt{Memo}
has much in common with technologies as early as Linda and as recent as Java Spaces. It supports virtually all of the primitives that are found in tuple space systems.
\par

% Label
\label{pgfId-13773}
The interested reader will want to read about the message passing interface (MPI) and Java virtual machine (JVM). These systems fall into the “oldies, but goodies” category. Despite being old and predominantly implemented in the C language, they address many other important factors in parallel programming. For example,
\texttt{Memo}
requires some hand holding to ensure that the various processes are all numbered correctly. (JVM and MPI have always provided a good amount of support for numbering at the expense of complexity. MPI has over 125 functions;
\texttt{Memo}
has fewer than 10 functions.) At present, this process must be done in a completely manual fashion. This decision has been made intentionally, because we are working on a research project called the Computational Neighborhood (we being J. Shafaee, G. Thiruvathukal, A. Singh, and T.W. Christopher) that addresses the issues of process management and job execution in a clustered environment. This framework makes use of the properties concept in Java and basically binds a set of properties for multipart jobs (Memo is just one variety of a multipart job). With relatively minor changes,
\texttt{Memo}
will be able to participate in the Computational Neighborhood without becoming a significantly more complex framework.
\par

% Label
\label{pgfId-13780}
You are invited to stay tuned to our latest tools and techniques for parallel and distributed programming. Please visit our Web site at http://www.toolsofcomputing.com and http://www.jhpc.cs.depaul.edu (or http://www.jhpc.org) for the latest updates to the code presented in this book, as well as our other open-source and research projects.
\par

\section{Exercises}

% Label
\label{pgfId-13822}

\begin{enumerate}

\item{Using the ideas of the vector-inner-product example, write a program that performs matrix multiplication in parallel. You will find it useful to break up the work into rows of the first matrix and columns of the second matrix. (You may find it useful to further consider the possibility of breaking up the work of computing the inner product of the row and column vectors using a variation on the VectorPair class for large runs.)}

\item{Design a version of GMI that is more like SMA (thus eliminating the dependence on Serializable ) where the CallMessage class allows you to set and get basic parameter types. Rewrite the Memo system to make use of the Message ideas instead of Serializable . This could be a lot of work. (You may also find that it is desirable for scientific applications to extend SMA to have support for basic arrays of int and float .)}

\item{Write a Memo program that makes use of the BigInteger class found in Java to compute the factors of a very large number in parallel on a network of computers. (You might find this useful, say, for cracking public-key encryption schemes. We suggest limiting the key size to something tractable, say, 64 bits.)}

\item{Use Memo to rework some of the algorithms presented earlier in the book.}

\end{enumerate}

% Footnotes Skipped
